import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-06-18
 * Time: 12:15
 */

public class TestDemo {

    //交换函数
    public static void swap(int array[],int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //9 6 5 3 2 4 8
    public static void InsertSort(int[] array) {
        //插入排序思想将i前面的元素看做成有序的，然后将i位置的元素插入到i前面的元素中
        for(int i =1;i<array.length;++i){
            int tmp = array[i];//将i位置的元素保存起来然后插入到i位置之前
            int j =i-1;
            for(;j >= 0;--j){
                 if(array[j]>tmp){
                     //如果j位置的元素大于tmp就将这个元素往后挪动一位
                     array[j+1] = array[j];
                 }else {
                     //否则的话跳出循环·应该放回j+1位置
                     break;
                 }
            }
            array[j+1] = tmp;
        }
    }

    public static void shellSort(int[] array){
        //gap的为一组，每次gap也在改变
        int gap = array.length;
        while(gap>1){

            for(int i = 0;i<array.length;++i){
                int tmp = array[i];
                int j = i-gap;
                for(;j>=0;j-=gap){
                    if(array[j]>tmp){
                        array[j+gap] = array[j];
                    }else {
                        break;
                    }
                }
            }
            gap/=3;
        }
        //InsertSort(array);
    }

    public static void selectSort(int array[]) {

        //从数组中选择一个最小的数字然后与前面的的元素进行交换
        for(int i =0;i<array.length;++i){
            int minIndex = i;
            for(int j = i;j<array.length;++j){
                if(array[j]<array[minIndex]){
                    swap(array,i,j);
                }
            }
        }
    }


    public static void bubbleSort(int[] array) {
        //冒泡排序
        for(int i = 0;i<array.length-1;++i){
            boolean flag = true;
            for(int j =0;j<array.length-1-i;++j){
                if(array[j]>array[j+1]){
                    swap(array,i,j);
                    flag = false;
                }
            }
            if(!flag){
                break;
            }
        }
    }

    private static void shiftDown(){

    }
    private static void createHeap(int[] array){
        for(int i =0;i<array.length;++i){

        }
    }
    public static void heapSort(int[] array) {

    }

    public static void main(String[] args) {
        int[] array = {9,6,8,5,3,2,4,7,8,9,6,60,31};
        //插入排序
        //InsertSort(array);
     //   System.out.println(Arrays.toString(array));
        //希尔排序
        //shellSort(array);
        //System.out.println(Arrays.toString(array));
       //选择排序
        //selectSort(array);
        //System.out.println(Arrays.toString(array));
        //冒泡排序
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
        //堆排序
        heapSort(array);
//        //快速排序
//        quickSort(array);
//        //归并排序
//        mergeSort(array);
//
    }

}
